package com.lun.medium;

import com.lun.util.BinaryTree.TreeNode;

public class FlipEquivalentBinaryTrees {
    public boolean flipEquiv(TreeNode root1, TreeNode root2) {
    	boolean[] flipFlag = {false}, allSameFlag = {true};
    	flipEquiv(root1, root2, flipFlag, allSameFlag);
    	return flipFlag[0] && allSameFlag[0];
    }
    
    private void flipEquiv(TreeNode root1, TreeNode root2, 
    		boolean[] flipFlag, boolean[] allSameFlag) {
    	
    	if(!allSameFlag[0]) return;
    	
    	if(root1 == null && root2 == null) {
    		flipFlag[0] = true;
    		return;
    	}
    	if(root1 != null && root2 != null) {
    		if(root1.val != root2.val) {
    			allSameFlag[0] = false;
    			return;
    		}
    		helper(root1.left, root1.right, root2.left, root2.right, flipFlag, allSameFlag);
    	}
    	
    	if(root1 == null ^ root2 == null) {
			allSameFlag[0] = false;
			return;
    	}
    }
    
    private void helper(TreeNode r1Left, TreeNode r1Right, TreeNode r2Left, TreeNode r2Right,//
    		boolean[] flipFlag, boolean[] allSameFlag) {
    	if(!allSameFlag[0]) return;
    	
    	boolean r1LeftExisted = r1Left != null;
    	boolean r1RightExisted = r1Right != null;
    	boolean r2LeftExisted = r2Left != null;
    	boolean r2RightExisted = r2Right != null;
    	
    	
    	if(r1LeftExisted && r1RightExisted && r2LeftExisted && r2RightExisted) {
    		if(r1Left.val == r2Right.val && r1Right.val == r2Left.val) {
    			flipFlag[0] = true;
    			flipEquiv(r1Left, r2Right, flipFlag, allSameFlag);
    			flipEquiv(r1Right, r2Left, flipFlag, allSameFlag);
    		}
    		
    		
    	}if(r1LeftExisted && !r1RightExisted && !r2LeftExisted && r2RightExisted) {
    		
    	}if(!r1LeftExisted && r1RightExisted && r2LeftExisted && !r2RightExisted) {
    		
    		
    	}else if(r1LeftExisted && !r1RightExisted && r2LeftExisted && !r2RightExisted) {
    		flipEquiv(r1Left, r2Left, flipFlag, allSameFlag);
    	}else if(!r1LeftExisted && r1RightExisted && !r2LeftExisted && r2RightExisted){
    		flipEquiv(r1Right, r2Right, flipFlag, allSameFlag);
    	}else if(!r1LeftExisted && !r1RightExisted && !r2LeftExisted && !r2RightExisted){
    		return;
    	}else{
			allSameFlag[0] = false;
			return;
    	}
    }
    
    
}
